# N皇后问题是指在N*N的棋盘上要摆N个皇后，要求任何两个皇后不同行、不同列， 也不在同一条斜线上。
# 给定一个整数n，返回n皇后的摆法有多少种。 n=1，返回1。 n=2或3，2皇后和3皇后问题无论怎么摆都不行，返回0。 n=8，返回92。


def n_queens(n: int):
    if n < 4:
        return 0

    record = [-1] * n

    return process(n, 0, record)


def process(n: int, i: int, record: list):
    if i == n:
        return 1

    res = 0
    for j in range(0, n):
        if is_valid(i, j, record):
            record[i] = j
            res += process(n, i+1, record)
    return res


def is_valid(i, j, record):
    for k in range(i):
        if record[k] == j or i-k == abs(record[k]-j):
            return False
    return True


if __name__ == "__main__":
    print(n_queens(8))
